package com.yequan.leetcode.recursion.isValidBST_98;

import com.yequan.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * //给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * //
 * // 假设一个二叉搜索树具有如下特征：
 * //
 * //
 * // 节点的左子树只包含小于当前节点的数。
 * // 节点的右子树只包含大于当前节点的数。
 * // 所有左子树和右子树自身必须也是二叉搜索树。
 * //
 * //
 * // 示例 1:
 * //
 * // 输入:
 * //    2
 * //   / \
 * //  1   3
 * //输出: true
 * //
 * //
 * // 示例 2:
 * //
 * // 输入:
 * //    5
 * //   / \
 * //  1   4
 * //     / \
 * //    3   6
 * //输出: false
 * //解释: 输入为: [5,1,4,null,null,3,6]。
 * //     根节点的值为 5 ，但是其右子节点值为 4 。
 * //
 * // Related Topics 树 深度优先搜索
 *
 * @author : Administrator
 * @date : 2020/3/29
 */
public class IsValidBST {

    private long lastValue = Long.MIN_VALUE;

    /**
     * 先中序遍历
     * 中序遍历中先访问了左子树最底层的左节点元素,然后一层一层往上访问
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        return helper(root);
    }

    private boolean helper(TreeNode root) {
        if (null == root) {
            return true;
        }
        if (!helper(root.left)) {
            return false;
        }
        if (root.val <= lastValue) {
            return false;
        }
        lastValue = (long) root.val;
        if (!helper(root.right)) {
            return false;
        }
        return true;
    }

}
